#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Software: PyCharm
# @Version : Python-
# @Author  : Shengji He
# @Email   : hsjbit@163.com
# @File    : PartitionEqualSubsetSum.py
# @Time    : 2020/10/11 20:44
# @Description:
from typing import List


class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        """
        Given a non-empty array nums containing only positive integers, find if the array can be partitioned into
        two subsets such that the sum of elements in both subsets is equal.

        Example 1:
            Input: nums = [1,5,11,5]
            Output: true
            Explanation: The array can be partitioned as [1, 5, 5] and [11].

        Example 2:
            Input: nums = [1,2,3,5]
            Output: false
            Explanation: The array cannot be partitioned into equal sum subsets.


        Constraints:
            - 1 <= nums.length <= 200
            - 1 <= nums[i] <= 100

        :param nums:
        :return:
        """
        n = len(nums)
        if n < 2:
            return False
        total = sum(nums)
        maxNum = max(nums)
        if total & 1:
            return False
        target = total // 2
        if maxNum > target:
            return False

        # dp = [[False] * (target + 1) for _ in range(n)]
        # for i in range(n):
        #     dp[i][0] = True
        #
        # dp[0][nums[0]] = True
        # for i in range(1, n):
        #     num = nums[i]
        #     for j in range(1, target + 1):
        #         if j >= num:
        #             dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num]
        #         else:
        #             dp[i][j] = dp[i - 1][j]
        # return dp[n - 1][target]
        dp = [True] + [False] * target
        for i, num in enumerate(nums):
            for j in range(target, num - 1, -1):
                dp[j] |= dp[j - num]
        return dp[target]


if __name__ == '__main__':
    S = Solution()
    # nums = [1, 2, 3, 5]
    nums = [1, 5, 11, 5]
    print(S.canPartition(nums))
    print('done')
